#include <stdio.h>
#include <stdlib.h>

// 定义图的最大节点数
#define MAX_NODES 1000

// 定义队列结构用于BFS
typedef struct {
    int items[MAX_NODES];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return q->front == -1;
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (q->rear == MAX_NODES -1) {
        printf("Queue is full!\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

// 出队操作
int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int item = q->items[q->front];
    q->front++;
    if (q->front > q->rear) {
        // 重置队列
        q->front = q->rear = -1;
    }
    return item;
}

// 主函数
int main() {
    int n, m; // n为节点数，m为边数
    printf("请输入节点数和边数（用空格分隔）：");
    scanf("%d %d", &n, &m);

    // 动态分配邻接表
    int **adjList = (int **)malloc(n * sizeof(int *));
    int *degree = (int *)calloc(n, sizeof(int)); // 记录每个节点的度数

    for (int i = 0; i < n; i++) {
        adjList[i] = (int *)malloc(n * sizeof(int)); // 最多n个邻居
        for (int j = 0; j < n; j++) {
            adjList[i][j] = 0; // 初始化为0（无连接）
        }
    }

    printf("请输入每条边的两个节点（从0到%d）：\n", n-1);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        // 无向图，双向连接
        adjList[u][degree[u]++] = v;
        adjList[v][degree[v]++] = u;
    }

    int start;
    printf("请输入起始节点v（从0到%d）：", n-1);
    scanf("%d", &start);

    // 初始化距离数组，-1表示未访问
    int *distance = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        distance[i] = -1;
    }
    distance[start] = 0; // 起始节点距离为0

    // 初始化队列并入队起始节点
    Queue q;
    initQueue(&q);
    enqueue(&q, start);

    // BFS遍历
    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        // 遍历当前节点的所有邻居
        for (int i = 0; i < degree[current]; i++) {
            int neighbor = adjList[current][i];
            if (distance[neighbor] == -1) { // 如果未被访问
                distance[neighbor] = distance[current] + 1;
                enqueue(&q, neighbor);
            }
        }
    }

    // 查找最远的节点
    int maxDistance = -1;
    int farthestNode = -1;
    for (int i = 0; i < n; i++) {
        if (distance[i] > maxDistance) {
            maxDistance = distance[i];
            farthestNode = i;
        }
    }

    if (farthestNode != -1) {
        printf("离节点 %d 最远的节点是 %d，距离为 %d。\n", start, farthestNode, maxDistance);
    } else {
        printf("没有与节点 %d 相连的其他节点。\n", start);
    }

    // 释放内存
    for (int i = 0; i < n; i++) {
        free(adjList[i]);
    }
    free(adjList);
    free(degree);
    free(distance);

    return 0;
}
